In computer storage devices (such as magnetic and optical disk drives) the bandwidth of the recording channel is limited, as well is the signal power. To achieve performance gains, various coding techniques are employed to increase the effective signal-to-noise ratio (SNR) by increasing the system's immunity to noise. This allows an increase in storage capacity by increasing the recording density while maintaining an arbitrarily low bit error rate.
There are generally two types of codes currently employed in recording devices: channel codes and error correction codes (ECC). Channel codes are directed at noise caused by a particular characteristic of the recording channel. For instance, a run-length limited (RLL) code is a channel code designed to attenuate noise due to intersymbol interference by limiting the minimum spacing between the pulses that represent the data symbols in the analog carrier signal. The spectral content of the data to be recorded may also adversely affect the system's ability to accurately detect the data upon readback; consequently, some data sequences may be harder to detect than others. To compensate for this phenomenon, a channel code for randomizing the data is commonly employed in recording devices which effectively "whitens" the data by randomizing it before writing the data to the disk storage medium. Upon read back, the recording channel is able to detect the randomized data at a lower bit error rate than if the data is not randomized. The data read from the storage medium is derandomized before being transferred to the host.
In error correction coding (ECC), the binary data to be recorded are processed mathematically to generate redundancy symbols that are appended to the data to form codewords which are written to the disk storage medium. Upon readback, the recorded codewords are estimated (detected) from the read signal, and the redundancy symbols are used to decode the estimated codewords back into the originally recorded user data. The redundancy symbols provide, in effect, a buffer which shields the codeword from noise as it passes through the recording channel. When enough noise "penetrates" this buffer, it mutates a written codeword into a different received codeword, thereby resulting in an error when decoded into the user data.
The more redundancy symbols employed in an error correction code, the larger the buffer around the codeword and the more noise that can be tolerated before a decoding error occurs. However, there is an upper bound on the performance of any given recording channel known as the "channel capacity" which refers to the maximum user data transmission rate (or recording density) achievable for a given channel while maintaining an arbitrarily low bit error rate. Ultimately, the channel capacity is a function of the channel bandwidth and the signal to noise (SNR) ratio. As mentioned above, channel codes and error correction codes are a means for improving performance by increasing the effective SNR.
There are many approaches to encoding/decoding the user data in order to maximize the reliability and efficiency of a recording channel; ultimately, the goal is to design a system that approaches the channel capacity while minimizing the implementation complexity and cost. Block error correcting codes are commonly employed in disk storage systems, particularly the Reed-Solomon block code due to its excellent error correction properties and low implementation cost and complexity.
Block codes encode a k-symbol input block of the source data stream into an n-symbol output block or codeword where n-k is the number of redundancy symbols and k/n is referred to as the code rate. The codewords are then transmitted through (stored to) the communication medium and decoded by the receiver. The encoding process performs a mathematical operation over the input block such that the output codewords are different from one another by a parameter referred to as the minimum distance of the code d.sub.min. The minimum distance d.sub.min between codewords determines the amount of noise that the system can tolerate before a received codeword is decoded erroneously.
With Reed-Solomon codes, the data stream is processed as a sequence of symbols, where the symbols are typically selected from a finite field GF(2.sup.w). The parameter w denotes the number of binary data bits per symbol. Each symbol of the k-symbol input block represents the coefficients of a data polynomial D(x). The redundancy symbols (which are also represented as a polynomial W(x)) are then computed as the modulo division of the input data polynomial D(x) divided by a generator polynomial G(x): EQU W(x)=(x.sup.m .multidot.D(x))MODG(x)
where m is the degree of the generator polynomial which equals the number of redundancy symbols. The redundancy polynomial W(x) is then added to the data polynomial D(x) to generate a codeword polynomial C(x): EQU C(x)=(x.sup.m .multidot.D(x))+W(x).
Those skilled in the art understand that the encoder circuitry for performing the above operations can be implemented with minimum cost using a linear feedback shift register (LFSR).
After encoding, the codeword C(x) is transmitted through the noisy communication channel, wherein the received codeword C'(x) equals the transmitted codeword C(x) plus an error polynomial E(x). The received codeword C'(x) is corrected according to the following steps: (1) compute error syndromes S.sub.i ; (2) compute the coefficients of an error locator polynomial using the error syndromes S.sub.i ; (3) compute the roots of the error locator polynomial, the logs of the roots are the error locations L.sub.i ; and (4) compute the error values using the error syndromes S.sub.i and the roots of the error locator polynomial.
The error syndromes S.sub.i are computed as the modulo division of the received codeword polynomial C'(x) divided by the factors of the generator polynomial G(x): EQU S.sub.i =C'(x)MOD(x+.alpha..sup.i)
when ##EQU1## where .alpha. is a primitive element of the finite field GF(2.sup.w) Techniques for performing the other steps of the decoding process, computing the error locator polynomial, computing the roots of the error locator polynomial, and computing the error values, are well known by those skilled in the art and are not necessary to understand the present invention. See, for example, the above referenced U.S. Pat. No. 5,446,743 entitled "COEFFICIENT UPDATING METHOD AND APPARATUS FOR REED-SOLOMON DECODER."
Another technique known in the prior art to further increase the error tolerance is to arrange the codewords into what is known as a multi-dimensional or product code. Digital Video Disk (DVD) storage systems, for example, commonly employ a two-dimensional product code shown in FIG. 3A. The codewords are arranged into intersecting horizontal (row or Q) and vertical (column or P) codewords and the decoding process is carried out in iterative passes. First a pass over the horizontal codewords is performed to correct as many errors as possible; any uncorrectable horizontal codewords are left unmodified. Then a pass is made over the vertical codewords to correct as many errors as possible, where a symbol corrected in a vertical codeword also corrects the corresponding symbol for the intersecting horizontal codeword. Consequently, the horizontal codeword may be correctable during the next horizontal pass. Similarly, a symbol corrected during a horizontal pass may render a previously uncorrectable vertical codeword correctable during the next vertical pass. This iterative process continues until the entire product code is corrected, or deemed uncorrectable.
The two-dimensional product code of FIG. 3A also comprises CRC redundancy symbols which are used to check the validity of the corrections to the row and column codewords. The CRC redundancy is typically generated by processing the user data according to EQU CRC redundancy=P(x).multidot.x.sup.n-k modG(x)
where P(x) is the user data represented as a polynomial having coefficients in a finite field GF(2.sup.m), n-k is the number of CRC redundancy symbols, and G(x) is a generator polynomial. The CRC redundancy is then appended to the user data before the resulting code word C(x) is written to the disk. During a read operation, the data read from the disk are processed to generate a CRC syndrome S.sub.CRC according to EQU S.sub.CRC =C'(x)modG(x),
where C'(x) is the received code word polynomial (including the CRC redundancy) read from the disk. If the codeword C'(x) is error-free, then the syndrome S.sub.CRC will be zero.
The CRC redundancy are typically generated over the data during a write operation before encoding the ECC redundancy symbols, and the CRC syndrome is generated during a read operation after the ECC redundancy are used to correct the product code. In this manner, the CRC syndrome operates to validate the corrections and to detect miscorrections. This is an extremely important function because it prevents the error correction system from passing "bad data" to the host system.
An overview of a prior art error correction system typically found in a CD/DVD optical disk storage system is shown in FIG. 1. During a write operation (assuming the device is not read only) user data received from a host system are stored in a data buffer 1. A CRC generator-and-correction validator 2 then reads the user data from the buffer over line 3, generates the CRC redundancy symbols, and restores the user data with appended redundancy symbols back into the data buffer 1. Thereafter the data is again read from the data buffer 1 (including the CRC redundancy), randomized by a data randomizer 4, and the randomized data restored to the data buffer 1. A P/Q encoder/decoder 5 then reads the randomized data from the data buffer 1, and an ECC/syndrome generator 12 generates the ECC redundancy symbols for the P and Q codewords to form the two-dimensional product code shown in FIG. 3A. The individual P and Q codewords are restored to the data buffer 1 after appending the ECC redundancy symbols. Once the entire product code has been generated, it is read from the data buffer 1 and written to the optical storage medium 6.
If the system is configured for a compact disk (CD) data format, then additional redundancy, referred to as C1 and C2, are generated and appended to the data before writing it to the disk. Thus to facilitate the CD recording format, the error correction system comprises a C1 encoder/decoder 7, a C2 encoder/decoder 8, and an interleaver/deinterleaver 9 for implementing the well known Cross Interleave Reed-Solomon Code (CIRC). Typically a static RAM (SRAM) 10 is employed to implement the CIRC coding process; SRAM is much faster than dynamic RAM (DRAM), the latter being used to implement the data buffer 1.
During a read operation, the process is run in reverse. If configured for CD format, then the C1 and C2 decoders make preliminary corrections to the randomized data as it is read from the optical disk 6 and stored in the data buffer 1. Once a complete product code is available in the data buffer 1, the P/Q decoder 5 begins the iterative passes over the P and Q codewords to make further corrections. The ECC/syndrome generator generates ECC syndromes transmitted over line 13 to an error corrector 14. The error corrector uses the ECC syndromes to correct errors in the individual codewords as described above. If at the end of a P or Q pass all of the ECC error syndromes are zero, indicating that the product code is error free (unless miscorrected), then the randomized data is read from the data buffer 1 and derandomized by derandomizer 4. As the data is derandomized, it is processed by the CRC generator-and-correction validator 2 to generate the CRC syndrome. If the CRC syndrome is zero, indicating that the corrections to the P and Q codewords are valid and complete, then the data is again read from the data buffer 1, derandomized, and the derandomized data transferred to the host system. If the CRC syndrome is non-zero, indicating that the product code has been miscorrected, then the CRC generator-and-correction validator 2 sends an error message to the host system over line 11 wherein the host system will initiate a retry operation (i.e., attempt to reread the data from the disk).
A fundamental drawback of the prior art error correction system shown in FIG. 1 is that the data must be derandomized before performing the CRC validation step. This requires an additional buffer access to read the entire product code, derandomize the data, and generate the CRC syndrome as described above. Obviously this increases the latency of the storage system which is highly undesirable, especially for multi-media applications where large blocks of audio/video data must be read from the storage system in a continuous stream to achieve smooth, uninterrupted performance.
There is, therefore, a need for an error correction system in a computer storage device that avoids the latency associated with verifying the validity and completeness of corrections to a multi-dimensional code, such as a CD/DVD product code.